package com.mgq.algorithm.twotree;

/**
 * @author MaGuangQi
 * 二叉搜索树插入节点
 * @date 2022-02-25 10:58
 **/
public class InsertNodeAVL_701 {
    //改的前提是 先找到插入位置. 然后把node构建起来
    public static TreeNode insertIntoBST(TreeNode root, int val) {
        if(root==null) {
            //创建新节点,新节点的 左和右都是null
            return new TreeNode(val);
        }
        //套模板
        if(root.val>val){
            //将新节点放到root的左子树
           root.left= insertIntoBST(root.left, val);
        }
        if(root.val<val){
            //将新节点放到root的右子树
            root.right= insertIntoBST(root.right, val);
        }

        return root;
    }

    //二叉搜索树查询模板
    public static void BST(TreeNode root,int target){
        if (root.val==target){
            //找到了目标,做点什么
        }
        //当前值大于目标值,在左树查
        if(root.val>target){
            BST(root.left, target);
        }
        //当前值小于目标值,在右树查
        if(root.val<target){
            BST(root.right, target);
        }
    }

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node7 = new TreeNode(7);
        node4.left=node2;
        node4.right=node7;
        node2.left=node1;
        node2.right=node3;
        insertIntoBST(node4,5);

    }
}
